// ++++++++++++++++++++++++++++++++++++++++
// 《零基础Go语言算法实战》源码
// ++++++++++++++++++++++++++++++++++++++++
// Author:廖显东（ShirDon）
// Blog:https://www.shirdon.com/
// Gitee:https://gitee.com/shirdonl/goAlgorithms.git
// Buy link :https://item.jd.com/14101229.html
// ++++++++++++++++++++++++++++++++++++++++

package main

import (
	"fmt"
	"math"
)

// 返回乘以给定矩阵序列所需的最小标量乘法次数
func matrixChainOrder(p []int) int {
	// 给定矩阵序列的长度
	n := len(p)

	// 创建一个二维数组来存储每个矩阵子序列所需的最少数量的标量乘法
	m := make([][]int, n)
	for i := range m {
		m[i] = make([]int, n)
	}

	// 计算每个矩阵子序列所需的最小标量乘法次数
	for l := 2; l < n; l++ {
		for i := 1; i < n-l+1; i++ {
			j := i + l - 1
			m[i][j] = math.MaxInt32
			for k := i; k <= j-1; k++ {
				q := m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j]
				if q < m[i][j] {
					m[i][j] = q
				}
			}
		}
	}

	//返回将矩阵序列从 1 乘到 n-1 所需的最小标量乘法次数
	return m[1][n-1]
}

func main() {
	// 要相乘的矩阵序列
	p := []int{2, 2, 3, 1, 2, 3, 5}

	//计算乘以矩阵序列所需的最小标量乘法次数
	minCost := matrixChainOrder(p)

	//打印所需的最少标量乘法次数
	fmt.Println("矩阵乘法的最小成本：", minCost)
}

//$ go run matrixChainOrder.go
//矩阵乘法的最小成本： 41
